package pers.qianyu.month_202101.date_20210120;

import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 101. 对称二叉树
 * https://leetcode-cn.com/problems/symmetric-tree/
 *
 * @author mizzle rain
 * @date 2021-01-20 14:05
 */
public class IsSymmetric2 {
    // 迭代法
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> lst = new LinkedList<>(), rst = new LinkedList<>();
        TreeNode pl = root.left, pr = root.right;
        while (pl != null || pr != null || !lst.isEmpty() || !rst.isEmpty()) {
            while (pl != null && pr != null) {
                lst.push(pl);
                rst.push(pr);
                pl = pl.left;
                pr = pr.right;
            }
            if (!(pl == null && pr == null)) return false;
            pl = lst.poll();
            pr = rst.poll();
            if (pl.val != pr.val) return false;
            pl = pl.right;
            pr = pr.left;
        }
        return true;
    }
}
